package search;


/**
 * @author zhm
 * @date 2020/10/20
 */
public class BinarySearch {

    /**
     * 普通的二分查找
     * @param arr
     * @param value
     * @return
     */
    public static int search(int arr[],int value){
        if(arr==null){
            return -1;
        }
        int low = 0;
        int high = arr.length-1;
        while (low<=high){
            int mid = low + ((high-low)>>1);
            if(arr[mid]==value){
                return mid;
            }else if(arr[mid]<value){
               low = mid + 1;
            }else {
                high = mid - 1;
            }
        }
        return -1;
    }

    /**
     * 查找出数组中第一个等于指定值的下标
     * @param a
     * @param value
     * @return
     */
    public static int searchFirstEqualValue(int[] a,int value){

        if(a==null || a.length<=0){
            return -1;
        }

        int low = 0;
        int high = a.length-1;
        while (low<=high){
            int mid = low + ((high-low)>>1);
            if(a[mid] == value){
                if((mid==0 || a[mid-1]!=value)){
                    return mid;
                }else {
                    high = mid -1;
                }
            }else if(a[mid]<value){
                low = mid + 1;
            }else {
                high = mid -1;
            }
        }
        return -1;
    }

    /**
     * 查找出数组中最后一个等于指定值的下标
     * @param a
     * @param value
     * @return
     */
    public static int searchLastEqualValue(int[] a,int value){

        if(a==null || a.length<1){
            return -1;
        }
        int low = 0;
        int high = a.length-1;
        while (low<=high){
            int mid = low + ((high-low)>>1);
            if(a[mid]==value){
                if((mid==a.length-1 || a[mid+1]!=value)){
                    return mid;
                }else {
                    low = mid + 1;
                }
            }else if(a[mid]<value){
                low = mid + 1;
            }else {
                high = mid -1;
            }
        }

        return -1;
    }

    /**
     * 查找第一个指定大于某个值的下标
     * @param a
     * @param value
     * @return
     */
    public static int searchFirstBigValue(int[] a,int value){

        if(a==null || a.length<1){
            return -1;
        }

        int low = 0;
        int high = a.length-1;

        while (low<=high){
            int mid = low + ((high-low)>>1);
            if(a[mid]>value){
                if(mid==0 || a[mid-1]<=value){
                    return mid;
                }else {
                    high = mid - 1;
                }
            }else {
                low = mid + 1;
            }
        }

        return -1;
    }

    /**
     * 查找最后一个小于某个值的下标
     * @param a
     * @param value
     * @return
     */
    public static int searchLastLittleValue(int[] a,int value){

        if(a==null || a.length<1){
            return -1;
        }


        return -1;
    }

}
